package com.c2b.algorithm.leetcode.base;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/serialize-and-deserialize-bst/'>序列化和反序列化二叉搜索树(Serialize and Deserialize BST)</a>
 * <p>序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。</p>
 * <p>设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。</p>
 * <p>编码的字符串应尽可能紧凑。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [2,1,3]
 *      输出：[2,1,3]
 *
 * 示例 2：
 *      输入：root = []
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数范围是 [0,10^4]</li>
 *     <li>0 <= Node.val <= 10^4</li>
 *     <li>题目数据 保证 输入的树是一棵二叉搜索树。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/16 14:20
 */
public class LC0449SerializeAndDeserializeBST_M {

    public static class Codec {


        // Encodes a tree to a single string.

        /**
         * 对于二叉搜索树，给定「先序遍历」或者「后序遍历」，对其经过排序即可得到「中序遍历」。
         * <ul>
         *     <li>给定一棵二叉树的「先序遍历」和「中序遍历」可以恢复这颗二叉树。</li>
         *     <li>给定一棵二叉树的「后序遍历」和「中序遍历」也可以恢复这颗二叉树。</li>
         * </ul>
         */
        public String serialize(TreeNode root) {
            // 后序遍历
            List<Integer> list = new ArrayList<>();
            postorder(root, list);
            // s:[1, 2, 3, 4]
            String s = list.toString();
            // return：1, 2, 3, 4
            return s.substring(1, s.length() - 1);
        }

        private void postorder(TreeNode root, List<Integer> list) {
            if (root == null) {
                return;
            }
            postorder(root.left, list);
            postorder(root.right, list);
            list.add(root.val);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.isEmpty()) {
                return null;
            }
            String[] arr = data.split(", ");
            Deque<Integer> stack = new ArrayDeque<>();
            int length = arr.length;
            for (int i = 0; i < length; i++) {
                stack.addFirst(Integer.parseInt(arr[i]));
            }
            return construct(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);
        }

        private TreeNode construct(int lower, int upper, Deque<Integer> stack) {
            if (stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) {
                return null;
            }
            int val = stack.removeFirst();
            TreeNode root = new TreeNode(val);
            root.right = construct(val, upper, stack);
            root.left = construct(lower, val, stack);
            return root;
        }
    }
}
